/*Files compilation:
	
	nvcc Main.cu Parser.cpp Search.cpp -o exec -arch sm_20
	./exec
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <curand_kernel.h>
#include "Parser.h"
#include "Search.h"

//Compares two strings
__device__ int strcmp_device (char *word, char *value, int index, int size)
{
	for(int i = index; i < size; i++){
		if(word[i] == ',' && value[i - index] == '\0')
			return 0;
		if(word[i] < value[i - index])
			return -1;
		else
		if(word[i] > value[i - index])
			return 1;
	}
	return 1;
}

//Does the binary search inside of the device
 __device__ int search_kernel(char *str, char *value, Map *map, int max, int size, int *index) {

 int position;
 int begin = 0; 
 int end = max - 1;
 int cond = 0;

 while(begin <= end) {
 
  position = (begin + end) / 2;
  cond = strcmp_device(str, value, map[position].addBeg, size);
  *index = position;
  
  if(cond == 0){
	
	if(map[position].done == 1)
		return 0;
	
	else{
		//If a word was found, a flag is raised once
		atomicCAS(&(map[position].done), 0, 1);
		return 1;
		}
	}
  else if(cond < 0)
   begin = position + 1;
   
  else
   end = position - 1;
 }
 return 0;
}

//Creates a map of word's positions into the data block
__global__ void parser_kernel (Map *maps, char *block, int size)
{
	int index = 0;
	maps[0].addBeg = 0;
	
	//creating the map
	for(int i = 0; i < size; i++){
		if(block[i] == ','){
			maps[index].done = 0;
			index++;
			maps[index].addBeg = i + 1;
				
		}
	}

}

//Starts the random function with a specific seed
__global__ void setup_kernel (curandState *state, int seed)
{
	int id = threadIdx.x + blockIdx.x * BLOCKS;
	curand_init(seed, id, 0, &state[id]);
}

//Main function responsable to create a random word according to a word lengh
__global__ void generate_kernel (curandState *state, char *block, Map *map, int totalWords, int size, int *result, int lengh)
{
	int id = threadIdx.x + blockIdx.x * BLOCKS;
	int index;
	
	char word[50];
	
	curandState localState = state[id];
	
		//Gerenating a word
		for(int i = 0; i < lengh; i++)
			word[i] = curand(&localState) % 26 + 97;
		
		word[lengh] = '\0';

		//Searches for that word on the main block
		int cond = search_kernel(block, word, map, 65836, size, &index);
		if(cond){
			//Updating the result
			atomicInc((unsigned int *)result, totalWords + 1);
		}
	//Updating the state
	state[id] = localState;
}



int main()
{
	//Host statements
	FILE *file;
	int size, bytes;
	unsigned int totalWords, newWords;
	char *block, *aux;
	char **words;
	int lengh;
	
	//Starting the counters
	totalWords = 0;
	newWords = 0;
	
	file = fopen("palavras.txt", "r");
	
	//Getting the data base size
	fseek (file , 0 , SEEK_END);
	size = ftell (file);
	rewind (file);
	
	printf("Reading from the main file...\n");
	
	//Reading the data base
	block = (char *)malloc((size) * sizeof(char));
	bytes = fread(block, sizeof(char), size, file);
	
	printf("Allocating space for each word...\n");
	
	words = (char **)malloc((size/(MAXWORD - 1) + 2800000) * sizeof(char *));
	for(unsigned int i = 0; i < (size/(MAXWORD - 1) + 2800000); i++)
		words[i] = (char *) malloc((MAXWORD + 1) * sizeof(char));
		
	//Parse of words
	parse(words, &totalWords, block, bytes);
	
	printf("Sorting the words...\n");
	
	//Sortinh the words
	sort(words, totalWords);
	
	bytes = 0;
	
	//A new block allocation
	block = (char *)malloc((size/38) * sizeof(char));
	block[0] = '\0';
	
	printf("Filtering the main file...\n");
	
	//Deleting repeated words and spliting words greater than 5 characters
	for(int i = 1; i < totalWords; i++)
	{
		if(strcmp(words[i], words[i-1]) != 0)
		{
			strcat(block, words[i-1]);
			strcat(block, ",");
			lengh = strlen(words[i-1]);
			bytes += lengh + 1;
			newWords++;
		}
	}
	
	block[bytes] = '\0';
	
	fclose(file);
	free(words);
	
	//Starting the GPU processing
	
	//Device statements
	char *devWords;
	Map *devMaps;
	int *devResult, result = 0;
	curandState *devStates;
	
	//Allocating 
	cudaMalloc((void **)&devWords, bytes + 1);
	cudaMalloc((void **)&devMaps, newWords * sizeof(Map));
	cudaMalloc((void **)&devResult, sizeof(int));
	cudaMalloc((void **)&devStates, BLOCKS * BLOCKS * sizeof(curandState));
	
	cudaMemcpy(devWords, block, bytes, cudaMemcpyHostToDevice);
	cudaMemset(devResult, 0, sizeof(int));
	
	printf("Words parsing...\n");
	
	//Creating a word map
	parser_kernel<<<1,1>>>(devMaps, devWords, bytes);
	
	//Starting the random function by a random seed
	setup_kernel<<<BLOCKS, BLOCKS>>>(devStates, time(NULL));
	
	printf("Words generation\n");
	wordsAdjustment(&newWords);
	
	//Getting the time befone the execution
	float percentage = 0.1;
	time_t timeTotal[11];
	int j = 1;
	
	timeTotal[0] = time(NULL);
	
	//Main loop
	while(result < newWords){
		
		//Generating words
		generate_kernel<<<BLOCKS, BLOCKS>>>(devStates, devWords, devMaps, newWords, bytes, devResult, 1);
		generate_kernel<<<BLOCKS, BLOCKS>>>(devStates, devWords, devMaps, newWords, bytes, devResult, 2);
		generate_kernel<<<BLOCKS, BLOCKS>>>(devStates, devWords, devMaps, newWords, bytes, devResult, 3);
		generate_kernel<<<BLOCKS, BLOCKS>>>(devStates, devWords, devMaps, newWords, bytes, devResult, 4);
		generate_kernel<<<BLOCKS, BLOCKS>>>(devStates, devWords, devMaps, newWords, bytes, devResult, 5);
		
		//Transmiting the result from device to host
		cudaMemcpy(&result, devResult, sizeof(int), cudaMemcpyDeviceToHost);
		
		//Comparing the percentage results
		if(result >= percentage * newWords){
			timeTotal[j] = time(NULL) - timeTotal[0];
			printf("Found %.0f per cent of the words - %ld sec\n", percentage * 100, timeTotal[j]);
			j++;
			percentage += 0.1;
		}
		
	}
	
	timeTotal[10] = time(NULL) - timeTotal[0];
	printf("Found %.0f per cent of the words - %ld sec\n", percentage * 100, timeTotal[10]);
	
	cudaFree(devWords);
	cudaFree(devMaps);
	cudaFree(devStates);
	cudaFree(devResult);
	free(block);
	
return 0;
}
